/***************************************************************************************
 * Copyright (c) 2014-2024 Zihao Yu, Nanjing University
 *
 * NEMU is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *          http:
 *
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 *
 * See the Mulan PSL v2 for more details.
 ***************************************************************************************/

#include <isa.h>
#include <memory/paddr.h>
/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>
enum
{
  TK_NOTYPE = 256,
  TK_EQ,
  TK_DECIMAL,
  TK_HEXADECIMAL,
  TK_REG_NAME,
  TK_PLUS,
  TK_MINUS,
  TK_MULTIPLY,
  TK_DIVIDE,
  TK_LPAREN,
  TK_RPAREN,
  TK_NEQ,
  TK_AND,
  TK_DEREF,
  TK_NEG
};
static struct rule
{
  const char *regex;
  word_t token_type;
} rules[] = {

    {" +", TK_NOTYPE},
    {"0x[0-9a-fA-F]+", TK_HEXADECIMAL},
    {"\\$[a-zA-Z_][a-zA-Z0-9_]*", TK_REG_NAME},
    {"[0-9]+", TK_DECIMAL},

    {"\\+", TK_PLUS},
    {"-", TK_MINUS},
    {"\\*", TK_MULTIPLY},
    {"/", TK_DIVIDE},

    {"==", TK_EQ},
    {"!=", TK_NEQ},
    {"&&", TK_AND},

    {"\\(", TK_LPAREN},
    {"\\)", TK_RPAREN}
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex()
{
  word_t i;
  char error_msg[128];
  word_t ret;

  for (i = 0; i < NR_REGEX; i++)
  {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0)
    {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token
{
  word_t type;
  char str[32];
} Token;

static Token tokens[256] __attribute__((used)) = {};
static word_t nr_token __attribute__((used)) = 0;

static bool make_token(char *e)
{
  word_t position = 0;
  word_t i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0')
  {

    for (i = 0; i < NR_REGEX; i++)
    {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0)
      {
        char *substr_start = e + position;
        word_t substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
        switch (rules[i].token_type)
        {
        case TK_NOTYPE:
          break;
        default:
          tokens[nr_token].type = rules[i].token_type;
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          tokens[nr_token].str[substr_len] = '\0';
          nr_token++;
          break;
        }

        break;
      }
    }

    if (i == NR_REGEX)
    {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

static word_t precedence(word_t type)
{
  switch (type)
  {
  case TK_LPAREN:
  case TK_RPAREN:
    return 6;

  case TK_DEREF:
  case TK_NEG:
    return 5;

  case TK_MULTIPLY:
  case TK_DIVIDE:
    return 4;

  case TK_PLUS:
  case TK_MINUS:
    return 3;

  case TK_EQ:
  case TK_NEQ:
    return 2;

  case TK_AND:
    return 1;

  default:
    return 0;
  }
}

static bool check_parentheses(word_t p, word_t q)
{
  if (tokens[p].type != TK_LPAREN || tokens[q].type != TK_RPAREN)
  {
    return false;
  }
  word_t balance = 0;
  for (word_t i = p; i <= q; i++)
  {
    if (tokens[i].type == TK_LPAREN)
    {
      balance++;
    }
    else if (tokens[i].type == TK_RPAREN)
    {
      balance--;
      if (balance == 0 && i < q)
      {
        return false;
      }
    }
  }
  return balance == 0;
}

static int eval(word_t p, word_t q, bool *success)
{
  if (*success == false)
  {
    return 0;
  }
  if (p > q)
  {
    *success = false;
    return 0;
  }

  if (p == q)
  {
    int val = 0;
    if(tokens[p].type == TK_REG_NAME)
    {
      bool reg_success = true;
      char *reg_name = tokens[p].str + 1;
      word_t val = isa_reg_str2val(reg_name, &reg_success);
      if (!reg_success) {
        *success = false;
        return 0;
      }
      return val;
    }else if(tokens[p].type == TK_HEXADECIMAL)
    {
      sscanf(tokens[p].str, "%x", &val);
    }else if (tokens[p].type == TK_DECIMAL)
    {
      sscanf(tokens[p].str, "%d", &val);
    }
    return val;
  }

  if (check_parentheses(p, q))
  {
    return eval(p + 1, q - 1, success);
  }

  int op = -1;
  int min_precedence = 10;
  int level = 0;
  for (int i = p; i <= q; i++)
  {
    if (tokens[i].type == TK_LPAREN)
    {
      level++;
    }
    else if (tokens[i].type == TK_RPAREN)
    {
      level--;
    }
    else
    {
      if (level == 0 && precedence(tokens[i].type) <= min_precedence && tokens[i].type != TK_DECIMAL && tokens[i].type != TK_HEXADECIMAL && tokens[i].type != TK_REG_NAME)
      {
        min_precedence = precedence(tokens[i].type);
        op = i;
      }
    }
  }

  if (op == -1)
  {
    printf("Error: cannot find an operator in tokens[%d..%d]\n", p, q);
    *success = false;
    return 0;
  }

  int val1 = 0;
  int val2 = 0;
  if (tokens[op].type == TK_DEREF || tokens[op].type == TK_NEG)
  {
    val2 = eval(op + 1, q, success);
  }
  else
  {
    val1 = eval(p, op - 1, success);
    val2 = eval(op + 1, q, success);
  }

  switch (tokens[op].type)
  {
  case TK_PLUS:
    return val1 + val2;
  case TK_MINUS:
    return val1 - val2;
  case TK_MULTIPLY:
    return val1 * val2;
  case TK_DIVIDE:
  {
    if (val2 == 0)
    {
      printf("Error: divide by zero\n");
      *success = false;
      return 0;
    }
    return val1 / val2;
  }
  case TK_EQ:
    return val1 == val2;
  case TK_NEQ:
    return val1 != val2;
  case TK_AND:
    return val1 && val2;
  case TK_DEREF:
    return paddr_read(val2, 4);
  case TK_NEG:
    return -val2;
  default:
    assert(0);
  }
}

word_t expr(char *e, bool *success)
{
  if (!make_token(e))
  {
    *success = false;
    return 0;
  }

  for (word_t i = 0; i < nr_token; i++)
  {
    if (tokens[i].type == TK_MULTIPLY)
    {

      if (i == 0 || tokens[i - 1].type == TK_PLUS || tokens[i - 1].type == TK_MINUS ||
          tokens[i - 1].type == TK_MULTIPLY || tokens[i - 1].type == TK_DIVIDE ||
          tokens[i - 1].type == TK_EQ || tokens[i - 1].type == TK_NEQ ||
          tokens[i - 1].type == TK_AND || tokens[i - 1].type == TK_LPAREN)
      {
        tokens[i].type = TK_DEREF;
      }
    }

    if (tokens[i].type == TK_MINUS)
    {

      if (i == 0 || tokens[i - 1].type == TK_PLUS || tokens[i - 1].type == TK_MINUS ||
          tokens[i - 1].type == TK_MULTIPLY || tokens[i - 1].type == TK_DIVIDE ||
          tokens[i - 1].type == TK_EQ || tokens[i - 1].type == TK_NEQ ||
          tokens[i - 1].type == TK_AND || tokens[i - 1].type == TK_LPAREN)
      {
        tokens[i].type = TK_NEG;
      }
    }
  }

  for (word_t i = 0; i < nr_token; i++)
  {
    printf("Token %d: type = %d, str = %s\n", i, tokens[i].type, tokens[i].str);
  }

  *success = true;
  word_t value = eval(0, nr_token - 1, success);
  if (*success == false)
  {
    return 0;
  }
  else
  {
    return value;
  }
}
